public class Graph {
	public int matrix1[][];
	public int n;
	public boolean directed;

	Graph(int V) {
		n = V;
		matrix1 = new int[V][V];
	}

	public void addEdge(int u, int v) {
		matrix1[u][v] = 1;
		if (!this.directed)
			matrix1[v][u] = 1;
	}

	public String toString() {
		String matrixString = "";
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (j == (n - 1)) {
					matrixString += matrix1[j][i] + "\n";
				} else {
					matrixString += matrix1[j][i] + "  ";
				}
		return matrixString;
	}

	public int degree(int v) {
		int deg = 0;
		for (int i = 0; i < n; i++) {
			deg += matrix1[v][i];
		}
		return deg;
	}

	public int inDegree(int v) {
		int inDeg = 0;
		for (int i = 0; i < n; i++) {
			inDeg += matrix1[i][v];
		}
		return inDeg;
	}

	public int outDegree(int v) {
		int outDeg = 0;
		for (int i = 0; i < n; i++) {
			outDeg += matrix1[v][i];
		}
		return outDeg;
	}

	public boolean isDirected() {
		return directed;
	}

	public String bfs(){
		return null;
	}
	
	public boolean cycle(int a, int b, int count){
		return(hasCycle(matrix1, a, b, count));
	}
	
	/**
     * Will determine if by adding an edge the graph will contain a cycle.
     * @param a The solution matrix of edges and vertices
     * @param edgeA One end of the edge to be added.
     * @param edgeB The other end of the edge to be added.
     * @param labCount The number of labs in the case.
     * @return false if there are no cycles, true if there is a cycle present.
     */
    public boolean hasCycle(int[][] b, int edgeA, int edgeB, int labCount){
    	
    	int[][] a = new int[labCount][labCount];
    	for(int i = 0; i < labCount; i++)
    		for(int j = 0; j < labCount; j++)
    			a[i][j] = b[i][j];
    	
    	//List that will hold the 
    	int[] visitedList = new int[labCount];
    	
    	//Perform DFS on the solution graph. This will add visited edges to the list.
    	DFS(a, visitedList);
    	
    	//If the two vertices from the edge to be added have already been visited, then a cycle will exist.
    	if(visitedList[edgeA] == 1 && visitedList[edgeB] == 1){
    		//Returning true means that a cycle will exist after adding the edge.
    		for(int i: visitedList){
    			System.out.println(i);
    		}
    		return true;
    	}
    	
    	//Return false will mean that adding the edge will not create a cycle.
    	for(int i: visitedList){
			System.out.println(i);
		}
    	return false;
    }
    
    /**
     * dfs, self explanatory. One modification, when visiting a vertex, it
     * will mark that visited vertex in the visitedList. 
     * @param matrix
     * @param v
     * @param visitList the list containing all the visited vertex's.  
     * @return
     */
    public String dfs(int[][] matrix, int v, int[] visitList) {
		for (int a = 0; a < matrix.length; a++) {
			if (matrix[v][a] == 1)
				matrix[v][a] = 0;
		}

		for (int i = 0; i < matrix.length; i++) {
			if (matrix[i][v] == 1) {
				//Mark the vertex as visited in the visitList
				visitList[i] = 1;
				return dfs(matrix, i, visitList);
			}
		}
		return null;
	}

	/**
	 * DFS algorithm. One modification, when visiting a vertex, it
     * will mark that visited vertex in the visitedList.
	 * @param matrix
	 * @param visitList
	 */
	public void DFS(int[][] matrix, int[] visitList){
		for(int i = 0; i < matrix.length; i++){
			for(int j = 0; j < matrix.length; j++){
				if(matrix[i][j] == 1){
					//Mark the vertex as visited in the visitList
					visitList[i] = 1;
					dfs(matrix, i, visitList);	
				}
			}
		}
	}
}